package class03;

import java.util.Arrays;

/**
 * @description: 在有序数组 arr 中，找到第一个 >=num 的位置
 * @time: 2021/7/7 21:37
 * @author: lhy
 */
public class BSFirstLeft {

    /** 二分搜索第一个 >= num 的数的索引
     * 二分搜索第一个 <= num 的数的索引 与此同理
     * @param arr 有序数组
     * @param num 待查值
     * @return index
     */
    public static int binarySearchFirstNoLessNumIndex(int[] arr, int num){
        if (arr == null || arr.length < 1){
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        int index = -1;
        while (l <= r){
            int mid = l + (r - l) / 2;
            if (arr[mid] >= num){
                index = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return index;
    }
    /**
     * 暴力求解方法
     * @param arr 有序数组
     * @param num 待查值
     * @return index
     */
    public static int test(int[] arr, int num){
        if (arr == null || arr.length < 1){
            return -1;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= num){
                return i;
            }
        }
        return -1;
    }

    /**
     * 生成随机有序数组
     * @param maxLen 数组最大长度
     * @param maxValue 数组最大值
     * @return arr
     */
    public static int[] generateRandomSoredArray(int maxLen, int maxValue){
        int len = (int) (Math.random() * maxLen );
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
        }
        Arrays.sort(arr);
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 10000;
        int maxLen = 1000;
        int maxValue = 1000;
        System.out.println(">>>Test start...");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomSoredArray(maxLen,maxValue);
            int num = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
            int indexB = binarySearchFirstNoLessNumIndex(arr,num);
            int indexT = test(arr,num);
            if (indexB != indexT){
                System.out.println("Error!");
                System.out.println(Arrays.toString(arr));
                System.out.println(indexB == -1 ? "-1" : arr[indexB]);
                break;
            }
        }
        System.out.println(">>>Test end.");
    }
}
